Leftist Heap
Operations
$ \mathtt{new}()
空のヒープを作成する
時間計算量$ \Theta(1)/ 空間計算量$ \Theta(1)
$ \mathtt{singleton}(x)
ただ一つの要素$ xからなるヒープを作成する
時間計算量$ \Theta(1)/ 空間計算量$ \Theta(1)
$ \mathtt{build}(x_1, x_2, \dots, x_n)
要素$ x_1, x_2, \dots, x_nからなるヒープを作成する
時間計算量$ \Theta(n)/ 空間計算量$ \Theta(n)
$ \mathtt{peek}()
ヒープの最小の要素を返す
時間計算量$ \Theta(1)
$ \mathtt{pop}()
ヒープの最小の要素を削除して返す
時間計算量$ \Omicron(\log n)
$ \mathtt{insert}(x)
ヒープに要素$ xを追加する
時間計算量$ \Omicron(\log n)
$ \mathtt{meld}(h)
ヒープ$ hの要素をすべて追加する
時間計算量$ \Omicron(\log n)
Summary
融合可能なヒープ (meldable heap) の一つ
$ \mathtt{meld}が基本的な操作で，$ \mathtt{insert}や$ \mathtt{pop}は$ \mathtt{meld}を用いて実装できる
$ \mathtt{insert}(x): $ \mathtt{meld}(\mathtt{singleton}(x))
$ \mathtt{pop}(x): 根の要素を取り出して左右の子同士を$ \mathtt{meld}
通常のヒープ順序に加えて，任意のノードについて左の子のランクが右の子のランク以上であるという不変条件 (leftist property) を保つ
ここでノードのランクはそのノードから空ノードまで右の子を辿っていったときの経路の長さとする
References
Chris Okasaki (1999) Purely Functional Data Structures. Cambridge University Press.
Notes
そのまま path-copying による永続化ができる
実は leftist property を維持することをやめても$ \mathtt{meld}は amortized$ \Omicron(\log n)を達成する → Skew Heap rank ではなく size に関して leftist property を保っても同じ計算量を達成する (weight biased)
size は部分木のノード数
heap 内の要素数を返す関数にそのまま対応できる利点がある
leftist property を維持せず、左右の内 rank が小さい方の部分木に再帰してもよい
Implementations
Problems